import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by L.jp
 * Description:N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
 * 要求：任何两个皇后不同行，不同列也不在同一条斜线上，
 * 求给一个整数 n ，返回 n 皇后的摆法数。
 * User: 86189
 * Date: 2022-08-17
 * Time: 22:01
 */
//我们利用一个结果集存储最终的结果，每一个符合的结果都作为一个临时的结果
public class Solution {
    public int Nqueen (int n) {
        return  getCount(n).size();
    }
    public List<List<String>> getCount(int n){
        char[][] cheer=new char[n][n];
        //布置初始棋盘
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cheer[i][j]='.';
            }
        }
        List<List<String>> ret=new ArrayList<>();
        //从第一行开始放
        setNQueen(ret,cheer,0);
        return ret;
    }
    
    private void setNQueen(List<List<String>> ret, char[][] cheer,int row) {
        //直到布置到了最后一行就可以返回了
        if(row==cheer.length){
            //把符合情况的数组变为临时结果的顺序表
            ret.add(getList(cheer));
            return;
        }
        //从每一行的第一列开始放置
        for(int col=0;col<cheer.length;col++){
            //判断是否是有效位置，必须保证同行同列同斜线没有皇后
            if(Valid(cheer,row,col)){
                //如果有效，那么放置皇后
                cheer[row][col]='Q';
                //布置下一行
                setNQueen(ret,cheer,row+1);
                //找到一组情况后，把遍历过的恢复为初始值
                cheer[row][col]='.';
            }
        }
    
    }
    
    private boolean Valid(char[][] cheer, int row, int col) {
        //同列的判断，row在变，同一个col,当我们传入的col不同时，就达到了同行同列判断的效果
        for(int i=0;i<row;i++){
            if(cheer[i][col]=='Q'){
                return false;
            }
        }
        //判断右上角
        for(int i=row-1,j=col+1;i>=0 && j< cheer.length;i--,j++){
            if(cheer[i][j]=='Q'){
                return false;
            }
        }
        //判断左上角斜线
        for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){
            if(cheer[i][j]=='Q'){
                return false;
            }
        }
        return true;
        
    }
    
    //把符合情况的结果二维数组也就是棋盘分布 转变为  一个存储了棋盘分布的顺序表，这样有利于加入到最终的结果
    private List<String> getList(char[][] cheer) {
        List<String> tmp=new ArrayList<>();
        for(int i=0;i< cheer.length;i++){
            tmp.add(new String(cheer[i]));
        }
        return tmp;
    }
}
